package tree.threadedBinaryTree;

public class ThreadedBinaryTreeDemo {

  private static Student root;

  public static void main(String[] args) {
    //测试一把中序线索二叉树的功能
    Student root = new Student(1, "tom");
    Student node2 = new Student(3, "jack");
    Student node3 = new Student(6, "smith");
    Student node4 = new Student(8, "mary");
    Student node5 = new Student(10, "king");
    Student node6 = new Student(14, "dim");

    //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
    root.setLeft(node2);
    root.setRight(node3);
    node2.setLeft(node4);
    node2.setRight(node5);
    node3.setLeft(node6);

    //测试中序线索化
    ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
    threadedBinaryTree.root=root;
    threadedBinaryTree.threadedNodes(root);

    //测试: 以10号节点测试
    Student leftNode = node5.getLeft();
    Student rightNode = node5.getRight();
    System.out.println("10号结点的前驱结点是 ="  + leftNode); //3
    System.out.println("10号结点的后继结点是="  + rightNode); //1

    // 遍历线索化二叉树
    System.out.println("遍历线索化二叉树");
    threadedBinaryTree.threadedList(root);


  }
}

class ThreadedBinaryTree {
  public Student root;
  public Student per=null;

  // 线索化二叉树
  public void threadedNodes(Student node) {
    if (node == null) {
      return;
    }
    threadedNodes(node.getLeft());

    if (node.getLeft()==null){
      node.setLeft(per);
      node.setLeftType(1);
    }

    if (per!=null&&per.getRight()==null){
      per.setRight(node);
      per.setRightType(1);
    }
    per=node;

    threadedNodes(node.getRight());

  }

  //遍历线索化二叉树
  public void threadedList(Student root){
    Student node=root;
    while (node!=null){

      while(node.getLeftType()==0){
        node=node.getLeft();
      }
      System.out.println(node);

      while (node.getRightType()==1){
        node=node.getRight();
        System.out.println(node);
      }

      node=node.getRight();
    }

  }

  // 前序遍历
  public void perOrder() {
    this.root.perOrder();
  }

  // 中序遍历
  public void midOrder() {
    this.root.midOrder();
  }

  // 后序遍历
  public void postOrder() {
    this.root.postOrder();
  }

  // 前序查找
  public Student perSearcher(int id) {
    Student result = null;
    if (this.root != null) {
      result = this.root.perSearcher(id);
    }
    return result;
  }
  // 中序查找
  public Student midSearcher(int id) {
    Student result = null;
    if (this.root != null) {
      result = this.root.midSearcher(id);
    }
    return result;
  }
  // 后序查找
  public Student postSearcher(int id) {
    Student result = null;
    if (this.root != null) {
      result = this.root.postSearcher(id);
    }
    return result;
  }

  // 删除结点
  public void delete(int id) {
    if (root == null) {
      System.out.println("数空");
    } else {
      if (root.getId() == id) {
        root = null;
      } else {
        root.delete(id);
      }
    }
  }
}

class Student {
  private int id;
  private String name;
  private Student left;
  private Student right;
  private int leftType;
  private int rightType;

  public Student(int id, String name) {
    this.id = id;
    this.name = name;
  }

  @Override
  public String toString() {
    return "Student{" + "id=" + id + ", name=" + name + '}';
  }

  public int getLeftType() {
    return leftType;
  }

  public void setLeftType(int leftType) {
    this.leftType = leftType;
  }

  public int getRightType() {
    return rightType;
  }

  public void setRightType(int rightType) {
    this.rightType = rightType;
  }

  public int getId() {
    return id;
  }

  public void setId(int id) {
    this.id = id;
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public Student getLeft() {
    return left;
  }

  public void setLeft(Student left) {
    this.left = left;
  }

  public Student getRight() {
    return right;
  }

  public void setRight(Student right) {
    this.right = right;
  }

  // 前序遍历
  public void perOrder() {
    System.out.println(this);
    if (this.left != null) {
      this.left.perOrder();
    }
    if (this.right != null) {
      this.right.perOrder();
    }
  }
  // 中序遍历
  public void midOrder() {

    if (this.left != null) {
      this.left.midOrder();
    }
    System.out.println(this);
    if (this.right != null) {
      this.right.midOrder();
    }
  }
  // 后序遍历
  public void postOrder() {

    if (this.left != null) {
      this.left.postOrder();
    }
    if (this.right != null) {
      this.right.postOrder();
    }
    System.out.println(this);
  }

  // 前序查找
  public Student perSearcher(int no) {

    if (this.id == no) {
      return this;
    }
    Student result = null;
    if (this.left != null) {
      result = this.left.perSearcher(no);
    }
    if (this.right != null) {
      result = this.right.perSearcher(no);
    }
    return result;
  }
  // 中序查找
  public Student midSearcher(int no) {
    Student result = null;
    if (this.left != null) {
      result = this.left.midSearcher(no);
    }
    if (this.id == no) {
      return this;
    }
    if (this.right != null) {
      result = this.right.midSearcher(no);
    }
    return result;
  }
  // 后序查找
  public Student postSearcher(int no) {
    Student result = null;
    if (this.left != null) {
      result = this.left.postSearcher(no);
    }
    if (this.right != null) {
      result = this.right.postSearcher(no);
    }
    if (this.id == no) {
      return this;
    }
    return result;
  }

  public void delete(int no) {
    if (this.left != null && this.left.id == no) {
      this.left = null;
      return;
    }
    if (this.right != null && this.right.id == no) {
      this.right = null;
      return;
    }
    if (this.left != null) {
      this.left.delete(no);
    }
    if (this.right != null) {
      this.right.delete(no);
    }
  }
}
